/**
 * 堆排序
 *
 * 还没弄明白
 */
public class HeapSort extends TemplateSort {

    @Override
    void sort(Comparable[] a) {
        int N = a.length;
         for (int k = N / 2; k >= 1; k--) {
             sink(a, k, N);
         }
         while (N > 1) {
             exch(a, 1, N--, true);
             sink(a, 1, N);
         }
    }

    /**
     * 重写模版类的less方法
     * @param a
     * @param i
     * @param j
     * @return
     */
    public boolean less(Comparable[] a, int i, int j) {
        return super.less(a[i - 1], a[j - 1]);
    }

    /**
     * 重写模版类的exch方法
     * @param a
     * @param i
     * @param j
     * @param heapExch
     */
    public void exch(Comparable[] a, int i, int j, boolean heapExch) {
        super.exch(a, i - 1, j - 1);
    }

    /**
     * 上浮（由下至上的堆有序化）
     * @param a
     * @param k
     */
    private void swim(Comparable[]a, int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(a, k / 2, k, true);
            k = k / 2;
        }
    }

    /**
     * 下沉（由上至下的堆有序化）
     * @param a
     * @param k
     * @param N
     */
    private void sink(Comparable[] a, int k, int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(a, j, j + 1)) {
                j++;
            }
            if (!less(a, k, j)) {
                break;
            }
            exch(a, k, j, true);
            k = j;
        }
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new HeapSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
